#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include "DoubleCircleLinkList.h"

//初始化
DoubleCircleLinkList::DoubleCircleLinkList()
{
    list->head = NULL;
    list->tail = NULL;
    list->len = 0;
}

//初始化，返回指针
DCList* DoubleCircleLinkList::DCList_Creat()
{
    DCList* pDLidst = new DCList;
    pDLidst->head = NULL;
    pDLidst->tail = NULL;
    pDLidst->len = 0;
    return pDLidst;
}


//创建节点
DCNode* DCList_CreateNode(ElementType element)
{
    DCNode* NewNode = new DCNode;
    NewNode->data = element;
    NewNode->prev = NULL;
    NewNode->next = NULL;
    return NewNode;
}

//释放
DoubleCircleLinkList::~DoubleCircleLinkList()
{
    //空表不释放
    if(list->len == 0)
        return;

    while(list->head != list->tail)
    {
        DCNode* freenode = list->head;
        list->head = list->head->next;
        delete(freenode);
    }
    delete(list->head);
    list->head = NULL;
    list->tail = NULL;
    list->len =0;
}

//遍历,自定义打印回调函数
void DoubleCircleLinkList::DCList_Travel(PrintCall printCall)
{
    if(list->len == 0)
        return;
    DCNode* cur = list->head;
    printf("next:\n");
    while(cur != list->tail)
    {
        printCall(cur->data);
        cur = cur->next;
    }
    printCall(list->tail->data);
    printf("\n");

    cur = list->tail;
    printf("prev:\n");
    while(cur != list->head)
    {
        printCall(cur->data);
        cur = cur->prev;
    }
    printCall(list->head->data);
    printf("\n");
}

//尾插
void DoubleCircleLinkList::DCList_InsertTail(ElementType element)
{
    DCNode* NewNode = DCList_CreateNode(element);
    if(NewNode == NULL)
    {
        printf("InsertTail create error!\n");
        return;
    } 
    if(list->len == 0)
    {
        list->head = NewNode;
        list->tail = NewNode;
    }
    else
    {
        list->tail->next = NewNode;
        NewNode->prev = list->tail;
        list->tail = NewNode;

        //link the head and tail
        list->tail->next = list->head;
        list->head->prev = list->tail;
    }
    list->len++;   
}

//头插
void DoubleCircleLinkList::DCList_InsertHead(ElementType element)
{
    DoubleCircleLinkList::DCList_InsertTail(element);
    if(list->len > 1)
    {
        list->tail = list->tail->prev;
        list->head = list->head->prev;
    }
}

//尾删
void DoubleCircleLinkList::DCList_PopBack()
{
    DoubleCircleLinkList::DCList_RemoveByIndex(list->len - 1);
}

//头删
void DoubleCircleLinkList::DCList_PopFront()
{
    DCList_RemoveByIndex(0); 
}

//按下标插入
DCList* DoubleCircleLinkList::DCList_InsertByIndex(int index, ElementType element)
{
    //头插
    DCNode* NewNode = DCList_CreateNode(element);
    if(index == 0)
    {
        NewNode->next = list->head;
        list->head->prev = NewNode;
        list->head = NewNode;
        NewNode->prev = list->tail;
        list->tail->next = NewNode;
        list->len++;
    }
    else
    {
        DCNode* cur = list->head;
        //找到要插入节点的前一个节点
        for(int i = 0; i < index - 1; ++i)
        {
            cur = cur->next;
        }
        //尾插
        if(cur == list->tail)
        {
            list->tail->next = NewNode;
            NewNode->prev = list->tail;
            list->tail = NewNode;

            //link the head and tail
            list->tail->next = list->head;
            list->head->prev = list->tail;
            list->len++;
        }
        else
        {
            //下标位置插入
            cur->next->prev = NewNode;
            NewNode->next = cur->next;
            cur->next = NewNode;
            NewNode->prev = cur;
            list->len++;
        }
    }
    return list;
}

//按位删除
void DoubleCircleLinkList::DCList_RemoveByIndex(int index)
{
    if(index < 0 || index > list->len)
    {
        printf("RemoveByIndex invalid space!\n");
        return;
    }
    if(index == 0)
    {
       //只有一个节点 
       if(list->len == 1)
       {
           free(list->head);
           list->head = NULL;
           list->tail = NULL;
           list->len = 0;
           return;
       }
       //删除第一个节点
       DCNode* freeNode = list->head;
       list->head = list->head->next;
       list->head->prev = list->tail;
       list->tail->next = list->head;
       free(freeNode);
       list->len--;
       return;
    }
    //删除最后一个节点
    if(index == list->len - 1)
    {
       DCNode* freeNode = list->tail;
       list->tail = list->tail->prev;
       list->tail->next = list->head;
       list->head->prev = list->tail;
       free(freeNode);
       list->len--;
       return;
    }

    DCNode* cur = list->head;
    while(index > 0)
    {
        cur = cur->next;
        index--;
    }
    DCNode* PrevNode = cur->prev;
    DCNode* NextNode = cur->next;
    PrevNode->next = cur->next;
    NextNode->prev = cur->prev;
    free(cur);
    list->len--;

}
//查找第一个值符合的元素
int DoubleCircleLinkList::DCList_FindFirstByElement(ElementType element, DataCompare dataCompare)
{
    int count = 0;
    DCNode* cur = list->head;
    while(cur != list->tail)
    {
        if(dataCompare(cur->data, element))
        {
            return count;
        }
        count++;
        cur = cur->next;
    }
    if(list->tail != NULL && list->tail->data == element)
        return count;
        
    return -1;
}
//按值删除
void DoubleCircleLinkList::DCList_RemoveByElement(ElementType element, DataCompare dataCompare)
{
     int index = DoubleCircleLinkList::DCList_FindFirstByElement(element, dataCompare);
    while(index != -1)
    {
        DoubleCircleLinkList::DCList_RemoveByIndex(index);
        index = DoubleCircleLinkList::DCList_FindFirstByElement(element, dataCompare);
    }
}

//查找下标所对应的值
ElementType DoubleCircleLinkList::DCList_FindByIndex(int index)
{
    if(list->len == 0)
    {
        printf("No data!\n");
    }
    DCNode* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    return cur->data;
}

//通过下标设定值
void DoubleCircleLinkList::DCList_SetValueByIndex(int index, ElementType element)
{
    DCNode* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    cur->data = element;
}

//更改元素值
void DoubleCircleLinkList::DCList_SetValueByElement(ElementType oldValue, ElementType newValue, DataCompare dataIsEqal)
{
    DCNode* cur = list->head;
    for(int i = 0; i < list->len; ++i)
    {
        if(dataIsEqal(cur->data, oldValue))
        {
            cur->data = newValue;
        }
        cur = cur->next;
    }
}

